1. Field of the Invention
The invention relates generally to a Reed-Solomon decoder circuit. More particularly, the invention relates to a forward Chien search type Reed-Solomon decoder circuit capable of performing a high speed cyclic redundancy check operation.
A claim of priority has been made to Korean Patent Application No. 2004-5646, filed on Jan. 29, 2004, the disclosure of which is hereby incorporated by reference in its entirety.
2. Description of the Related Art
Reed-Solomon (hereinafter, referred to as “RS”) code is a kind of Bose-Chaudhuri-Hocquenghem (hereinafter, referred to as “BCH”) code and is a linear block code. RS code is a kind of a block error correction code and is widely used in applications such as digital data communication and data storage. For example, RS code has found application in such varied products as hard disk drives (HDD), CDs, DVDs, barcodes, wireless and mobile communication systems, satellite communication systems, and digital television.
The need for error correction coding arises from the inevitable data or signal noise or data errors which result whenever data is stored to physical medium or transmitted over an imperfect communications channel. An RS encoder receives original data in a predetermined block format and adds redundant bits to the data to generate a codeword. An RS decoder receives the encoded data and related parity check data and recovers the original data when an error occurs because of transmission or storage.
FIG. 1 schematically shows a general error check and correction (hereinafter referred to as ECC) system associated with a data storage device. FIG. 1 shows an ECC system 100 for checking and correcting an error in data read or received by a data storage device. In general, the data storage device has an input port (NRZ IN) 12 and an output port (NRZ OUT) 14 forming respective date transmission channel interfaces. The data storage device has a buffer input port (BUF IN)16 and a buffer output port (BUF OUT) 18 forming separate buffer interfaces to (e.g.,) a memory storage core.
Assuming this general structure, and further assuming use of a cyclic redundancy check (hereinafter, referred to as CRC), ECC system comprise a CRC encoder 108 and an RS encoder 104 which respectively generate parity checks for data received through buffer input port BUF IN 16. In the case of decoding, forward error correction (hereinafter, referred to as “FEC”) is performed on the data transferred through the input port 12. A signal input through the input port 12 is transferred to both an RS decoder 102 and a CRC decoder 110. RS decoder 102 calculates a syndrome for the input signal, and CRC decoder 110 calculates a CRC operation value for the input signal.
If any one of the syndromes calculated by RS decoder 102 is not zero, a modified Euclid algorithm (hereinafter, “MEA”) unit 112 within RS decoder 102 calculates an error location polynomial (hereinafter, referred to as “ELP”) and an error pattern polynomial (hereinafter, referred to as “EPP”) using a competent MEA. MEA unit 112 outputs the calculation result to both a Chien search circuit 114 and a Forney algorithm circuit 116. The Chien search circuit 114 and the Forney algorithm circuit 116 perform Chien search and a Forney algorithm on an output signal from MEA unit 112, respectively. Chien search circuit 114 finds an error location for the transferred data using the Chien search, and Forney algorithm circuit 116 obtains an error pattern for the transferred data using the Forney algorithm. In order to check for a missed error correction after RS decoding, a CRC decoder 118 performs an additional CRC decoding using the error location and the error pattern obtained after RS decoding. If there is no error in the RS decoding result and the CRC decoding result, data is output through buffer output port 18.
FIG. 2 illustrates the operation of RS decoder 102 in some additional detail. Referring to FIG. 2, RS decoder 102 begins with obtaining a syndrome of a codeword for data r(x) received by the data storage device. A syndrome generator circuit 202 generates a syndrome polynomial S(x). If all the calculated syndromes are zero, an additional RS decoding is not performed. If the CRC operation value for the codeword is zero, it is ultimately determined that no error is found in the received data. If, however, the obtained syndrome is not zero, RS decoding is performed. At this time, the MEA unit 206 performs a MEA using error mode and erasure mode. The MEA unit 206 receives syndrome polynomial S(x) and an erasure polynomial λ(x) generated by an erasure generator 204, obtains an ELP σ(x) and an EPP ω(x), and outputs the ELP σ(x) and the EPP ω(x) to a Chien search circuit 208 and a Forney algorithm circuit 210 respectively. Chien search circuit 208 obtains an error location by performing a Chien search using the ELP σ(x) obtained following application of the MEA. Forney algorithm circuit 210 obtains an error pattern by applying the Forney algorithm using the EPP ω(x) obtained following application of the MEA.
Returning to FIG. 1, ECC system 100 also includes an additional CRC operator 120 to reduce miss-correction by RS decoder 102. This is accomplished by the CRC operator 120 performing a CRC encoding on data received from input port 12. CRC operator 120 includes a first CRC decoder 110 and a second CRC decoder 118. First CRC decoder 110 decodes data received from input port 12. Second CRC decoder 118 decodes data using the error location and the error pattern. First CRC decoder 110 receives a signal input through the input port 12 and performs CRC decoding on the received data. Second CRC decoder 118 performs CRC decoding using the error location and the error pattern obtained after RS decoding is performed. Where the CRC operation value for the data input through input port 12, as obtained by first CRC decoder 110, is identical to the CRC operation value for the error location and the error pattern obtained by the second CRC decoder 118, it is determined that no CRC error is found. As RS decoding is performed symbol by symbol, the first and second CRC decoders should operate symbol by symbol as well.
FIG. 3 shows one data format used widely for data stored in contemporary storage devices. Referring to FIG. 3, the data format includes a 512 byte data sector, a 2 byte embedded sector number (ESN), 4 bytes reserved for CRC operation, and 80 bytes reserved for RS operation. As noted, RS decoding and CRC decoding by the second CRC decoder are typically performed symbol by symbol. The RS decoder uses ELP(σ(x)) and EPP(ω(x)) as initial coefficients when implementing the Chien search and the Forney algorithm. When ELP(σ(x)) and EPP((ω(x)) are used as initial coefficients, the RS decoder should perform Chien search in a reverse order of receiving a message. Accordingly, the conventional RS decoder should store an error location and an error pattern and input the error location and the error pattern to the CRC decoder in a reverse order for the successive CRC operation.